In [1]:
%%HTML
<style>
.container { width:100% }
</style>
The function board_2_bitmap takes two parameters:
board is a numpy array representing a board.player is an integer from the set $\{1, -1\}$.It returns an integers encoding the position of the player as a bitstring.
48 49 50 51 52 53 54 55
+----------------------+
| 40 41 42 43 44 45 46 | 47 top row
| 32 33 34 35 36 37 38 | 39
| 24 25 26 27 28 29 30 | 31
| 16 17 18 19 20 21 22 | 23
| 8 9 10 11 12 13 14 | 15
| 0 1 2 3 4 5 6 | 7 bottom row
+----------------------+
In [2]:
top_line = (1 << 40) | (1 << 41) | (1 << 42) | (1 << 43) | (1 << 44) | (1 << 45) | (1 << 46)
top_line
Out[2]:
In [3]:
def bit_position(row, col):
return row * 8 + col
In [4]:
def get_bit(bitboard, row, col):
pos = bit_position(row, col)
return (bitboard >> pos) & 1
In [5]:
def set_bit(bitboard, row, col):
pos = bit_position(row, col)
return bitboard | (1 << pos)
In [6]:
def board_2_bitmap(board, player):
position = ''
for row in range(5+1):
for col in range(0, 6):
if board[row, col] == player:
position += '1'
else:
position += '0'
position += '0'
return int(position, 2)
Given a bitboard representing the pieces of one player, check whether there are four pieces in a horizontal, vertical, or diagonal line.
In [7]:
def has_four(bitboard):
shifts = [1, 7, 8, 9]
for s in shifts:
if bitboard & (bitboard >> s) & (bitboard >> (2 * s)) & (bitboard >> (3 * s)):
return True
return False
This notebook defines the game Connect Four. You can play it online at: http://www.connectfour.org/connect-4-online.php.
Connect Four is played on a $6 \times 7$ board. Instead of Red and Yellow we call the players Xand O. Player X starts. Player X and O take turns to choose columns that are not yet filled. When player X chooses column c, the first non-empty field in column c is filled with an "X". Likewise, when player O chooses column c, the first non-empty field in column c is filled with an "X". Rows are numbered from the bottom up, i.e. the bottom row is row $0$. The goal of the game for player X is to get four consecutive Xs into a row, column, or diagonal line, while player O needs to get four consecutive Os into a row, column, or diagonal line.
In [8]:
Players = [0, 1]
States are represented as pairs of bitboards. Additionally, there is a 7 tuple showing how many pieces have been put into each column.
In [9]:
Start = (0, 0)
Start
Out[9]:
The function find_empty takes two arguments:
State is a description of the board,col specifies a column, i.e. it is an integer from the set $\{0, \cdots, 6\}$.Given the State the function find_empty(State, col) returns the smallest $\texttt{row} \in \{0, \cdots, 5\}$ such that
State[row][col] == ' 'holds. If the specified column is already completely filled, then instead None is returned.
In [10]:
def find_empty(state, col):
b1, b2 = state
board = b1 | b2
for row in range(6):
if not get_bit(board, row, col):
return row
return 6
Given a State and the player who has the next move, the function next_states(State, player) computes the set of states that can be reached from State.
In [11]:
def next_states(state, player):
States = set()
board = state[player]
for col in range(7):
row = find_empty(state, col)
if row != 6:
new_board = set_bit(board, row, col)
if player == 0:
new_state = (new_board, state[1])
else:
new_state = (state[0], new_board)
States.add(new_state)
return States
The variable All_Lines collects the coordinates of all groups of four fields that are consecutive horizontally, vertically, or diagonally.
In [12]:
# horizontal lines
All_Lines = [ [ (row, col+x) for x in range(3+1) ] for col in range(4)
for row in range(6)
]
# vertical lines
All_Lines += [ [ (row+x, col) for x in range(4) ] for col in range(7)
for row in range(3)
]
# rising diagonals
All_Lines += [ [ (row+x, col+x) for x in range(4) ] for col in range(4)
for row in range(3)
]
# falling diagonals
All_Lines += [ [ (row+x, col-x) for x in range(4) ] for col in range(3, 7)
for row in range(3)
]
Given a State the function top_line_filled(State) checks whether all marks in the top line of the given board are filled.
In [13]:
def top_line_filled(state):
b1, b2 = state
board = b1 | b2
return top_line & board == top_line
The function utility takes two arguments:
State is a tuple of tuple representing the board.player is a player.The function returns 1 if player has won the game, -1 if the game is lost for player, 0 if its a draw, and None if the game has not yet been decided.
In [14]:
def utility(state, player):
b1, b2 = state
if has_four(b1):
return 1 - 2 * player
if has_four(b2):
return -1 + 2 * player
# no winner so far, check for a draw
if top_line_filled(state): # no empty squares
return 0
return None
The function heuristic tries to guess the value of a state. As it is never called in terminal states, it assumes that the game will be drawn.
In [15]:
def get_mark(state, row, col):
b1, b2 = state
if get_bit(b1, row, col):
return 'X'
if get_bit(b2, row, col):
return 'O'
return ' '
In [16]:
def heuristic(state, player):
b1, b2 = state
result = 0.0
# all lines are checked whether they contain either 3 or 2 identical nonempty marks
for Line in All_Lines:
List = []
for row, col in Line:
mark = get_mark(state, row, col)
if mark != ' ':
List.append(mark)
if len(List) == 3:
Chars = set(List)
if len(Chars) == 1:
if Chars == { player }:
result += 1/10
else:
result -= 1/10
if len(List) == 2:
Chars = set(List)
if len(Chars) == 1:
if Chars == { player }:
result += 1/100
else:
result -= 1/100
return result
finished(State) is True if the game is over.
In [17]:
def finished(state):
return utility(state, 0) != None
The function get_move asks the user to input a move in the format r,c where r is the row and the c is the column where the next symbol is to be placed.
In [18]:
def get_move(state):
b1, b2 = state
while True:
col = input("Enter column here: ")
col = int(col)
row = find_empty(state, col)
if row != 6:
b2 = set_bit(b2, row, col)
return b1, b2
else:
print("Don't cheat. Please try again.")
This function informs the user about the result of the game once the game is finished.
In [19]:
def final_msg(State):
if finished(State):
if utility(State, 1) == 1:
print("You have won!")
elif utility(State, 1) == -1:
print("You have lost!")
else:
print("It's a draw.");
return True
return False
In [20]:
import ipycanvas as cnv
In [21]:
size = 50
This function creates the canvas for the start state. It draws an empty board which is later used for the game.
In [22]:
def create_canvas(Start):
n = len(Start)
canvas = cnv.Canvas(size=(size * 7, size * 8))
display(canvas)
return canvas
In [23]:
import math
The function draw takes three arguments:
State is the current state of the game.canvas is a canvas used to draw the state.value is the value of the game for player X.The function draws the given State onto canvas. Below that, the value is printed.
In [24]:
def draw(state, canvas, value):
b1, b2 = state
canvas.clear()
canvas.font = '36px sans-serif'
canvas.text_align = 'center'
canvas.text_baseline = 'middle'
for row in range(6):
for col in range(7):
x = col * size
y = row * size
canvas.line_width = 3.0
canvas.stroke_rect(x, y, size, size)
x += size // 2
y += size // 2
s1 = get_bit(b1, 5 - row, col)
s2 = get_bit(b2, 5 - row, col)
if s1 != 0:
canvas.fill_style ='red'
canvas.fill_arc(x, y, 0.4*size, 0, 2*math.pi)
if s2 != 0:
canvas.fill_style ='blue'
canvas.fill_arc(x, y, 0.4*size, 0, 2*math.pi)
canvas.font = '20px sans-serif'
canvas.fill_style = 'black'
for i in range(7):
x = (i + 0.5) * size
y = 6.4 * size
canvas.fill_text(str(i), x, y)
x = 3.5 * size
y = 7.4 * size
canvas.fill_text(str(value), x, y)
In [ ]: